#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 并查集
class UF {
    int cnt;
    vector<int> parent;

  public:
    UF(int n) {
        cnt = n;
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int findParent(int x) {
        if (parent[x] != x) parent[x] = findParent(parent[x]);
        return parent[x];
    }

    bool connected(int x, int y) {
        int xp = findParent(x);
        int yp = findParent(y);
        return xp == yp;
    }

    int count() { return cnt; }

    void Union(int x, int y) {
        int xp = findParent(x);
        int yp = findParent(y);
        if (xp == yp) return;
        cnt--;
        parent[yp] = xp;
    }
};

int kruskal(int n, vector<vector<int>>& cost) {
    // 对边排序
    sort(cost.begin(), cost.end(),
         [](auto& a, auto& b) { return a[2] < b[2]; });

    UF uf(n + 1);
    int ans = 0;

    for (int i = 0; i < cost.size(); i++) {
        if (uf.count() == 2) break;
        if (uf.connected(cost[i][0], cost[i][1])) continue;
        uf.Union(cost[i][0], cost[i][1]);
        ans += cost[i][2];
    }

    return ans;
}
